package com.wangjw.interview.loop;

/**
 * Created by wangjw on 18/5/9.
 */
public class BinarySearch {

    /**
     * Searches element k in sorted array.
     * @param arr a sorted array
     * @param k the element to search
     * @return index in arr where k is. -1 if not found
     */
    public int binarySearch(int[] arr, int k) {
        int a = 0;
        int b = arr.length;

        while (a < b) {
            int m = a + (b - a) / 2; // (a + b) / 2 may overflow!
            if (k < arr[m]) {
                b = m;
            } else if (k > arr[m]) {
                a = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        BinarySearch binarySearch = new BinarySearch();
        System.out.println(binarySearch.binarySearch(new int[] {1, 2, 10, 15, 100}, 15));
        System.out.println(binarySearch.binarySearch(new int[] {1, 2, 10, 15, 100}, -2));
        System.out.println(binarySearch.binarySearch(new int[] {1, 2, 10, 15, 100}, 101));
        System.out.println(binarySearch.binarySearch(new int[] {1, 2, 10, 15, 100}, 13));
        System.out.println("========");

        System.out.println(binarySearch.binarySearch(new int[] {}, 13));
        System.out.println(binarySearch.binarySearch(new int[] {12}, 13));
        System.out.println(binarySearch.binarySearch(new int[] {13}, 13));
        System.out.println("========");

        System.out.println(binarySearch.binarySearch(new int[] {12, 13}, 12));
        System.out.println(binarySearch.binarySearch(new int[] {12, 13}, 13));
        System.out.println("========");
    }
}
